//
// Created by CodeZijun on 2022/12/1.
//
#include "BinTree.h"
//层序栈建树
void binTree::produceTree() {
    string tmp;
    queue<binTreeNode*> q;
    cin>>tmp;
    if(tmp=="$"||tmp=="#")
        return;
    else {
        root = new binTreeNode;
        root->data = tmp;
        q.push(root);
    }
    while(!q.empty()){
        cin>>tmp;
        if(tmp=="$")
            break;
        else if(tmp!="#"){
            binTreeNode* node = new binTreeNode;
            node->data = tmp;
            q.front()->l_child = node;
        }
        cin>>tmp;
        if(tmp=="$")
            break;
        else if(tmp!="#"){
            binTreeNode* node = new binTreeNode;
            node->data = tmp;
            q.front()->r_child = node;
        }
        binTreeNode* p = q.front();
        if(p->l_child != nullptr)
            q.push(p->l_child);
        if(p->r_child != nullptr)
            q.push(p->r_child);
        q.pop();
    }
    cout<<"Completely Build!"<<endl;
    pre = root;
}

//前序遍历
void binTree::preOrder(binTreeNode* p) {
    if(!p) return;
    else{
    	cout<<p->data<<" ";
        preOrder(p->l_child);
        preOrder(p->r_child);
    }
}

//后序遍历
void binTree::aftOrder(binTreeNode *p) {
    if(!p) return ;
    else{
        aftOrder(p->l_child);
        aftOrder(p->r_child);
        cout<<p->data<<" ";
    }
}

//中序遍历
void binTree::midOrder(binTreeNode *p) {
    if(!p) return ;
    else{
        midOrder(p->l_child);
        cout<<p->data<<" ";
        midOrder(p->r_child);
    }
}

//层序遍历
void binTree::levOrder(binTreeNode *p) {
    if(!p) return;
    else{
        queue<binTreeNode*> q;
        q.push(p);
        while(!q.empty())
        {
            binTreeNode* ft = q.front();
            cout<<ft->data<<" ";
            q.pop();
            if(ft->l_child != nullptr)
                q.push(ft->l_child);
            if(ft->r_child != nullptr)
                q.push(ft->r_child);
        }
    }
}
